package org.example.struct.array2;

import java.util.Arrays;

/**
 * @author liyishan
 * @date 2023/10/11 09:24
 * @apiNote
 */

public class Test00611TriangleNumber {


    public static void main(String[] args) {
        int[] nums = {2, 2, 3, 4};
        int ans = test(nums);
        System.out.println(ans);
    }

    public static int test(int[] nums) {
        int len = nums.length;
        int ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int left = j + 1, right = len - 1, k = j;
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (nums[mid] - nums[j] < nums[i]) {
                        k = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                ans += k - j;
            }
        }
        return ans;
    }

    public static int test1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int k = i;
            for (int j = i + 1; j < n; j++) {
                while (k + 1 < n && nums[k + 1] < nums[j] + nums[i]) {
                    k++;
                }
                ans += Math.max(k - j, 0);
            }
        }
        return ans;
    }

    public static int test2(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = 0;
        for (int i = n - 1; i >= 2; i--) {
            int l = 0, r = i - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[i]) {
                    res += r - l;
                    r--;
                } else {
                    l++;
                }
            }
        }
        return res;
    }

    public static int test3(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int s = nums[i] + nums[j];
                int l = j + 1, r = n - 1;
                while (l < r) {
                    int mid = l + r + 1 >>> 1;
                    if (nums[mid] < s) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                if (nums[r] < s) {
                    res += r - j;
                }
            }
        }
        return res;
    }


}
